package org.example.myleet.rosalind.nwck;

import org.example.myleet.rosalind.utils.NewickTreeNode;
import org.example.myleet.rosalind.utils.NewickTreeUtil;

import java.io.*;
import java.util.*;

public class Solution{

    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        BufferedReader bf = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
        List<String> lines = new LinkedList<>();
        String line;
        while (null != (line = bf.readLine())) {
            lines.add(line);
        }
        Iterator<String> it = lines.iterator();
        while (it.hasNext()) {
            line = it.next();
            if (line.length() < 1) {
                continue;
            }
            String serialized = line;
            NewickTreeNode root = NewickTreeUtil.parse(null, serialized);
            line = it.next();
            String[] values = line.split(" ");
            int distance = solution.findNodesDistance(root, values[0], values[1]);
            System.out.printf("%d ", distance);
        }
        System.out.println();
        bf.close();
    }

    public int findNodesDistance(NewickTreeNode root, String v1, String v2) {
        NewickTreeNode node1 = findValueInTree(root, v1);
        if (null == node1) {
            throw new IllegalStateException(v1 + " not found!");
        }
        int distance = 0;
        Set<Integer> visited = new HashSet<>();
        Queue<NewickTreeNode> queue = new LinkedList<>();
        queue.offer(node1);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                NewickTreeNode node = queue.poll();
                if (null != node) {
                    if (visited.contains(node.getId())) {
                        continue;
                    }
                    if (node.getValue().endsWith(v2)) {
                        return distance;
                    }
                    queue.offer(node.getParent());
                    visited.add(node.getId());
                    for (NewickTreeNode child : node.getChildren()) {
                        queue.offer(child);
                    }
                }
            }
            ++distance;
        }
        System.out.print("*");
        return distance;
    }

    private NewickTreeNode findValueInTree(NewickTreeNode root, String v) {
        Queue<NewickTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                NewickTreeNode node = queue.poll();
                if (null != node) {
                    if (node.getValue().endsWith(v)) {
                        return node;
                    }
                    for (NewickTreeNode child : node.getChildren()) {
                        queue.offer(child);
                    }
                }
            }
        }
        return null;
    }
}
